package codingforgreat.class03;


import com.sun.xml.internal.ws.api.model.wsdl.editable.EditableWSDLBoundFault;

import java.util.HashMap;

//动规和滑动窗口都做一下比较一下时间复杂度
// 本题测试链接 : https://leetcode.com/problems/longest-substring-without-repeating-characters/
public class Class01_LongestSubstringWithoutRepeatingCharacters {
    public static int lengthOfLongestSubstring(String s) {
        if (s == null || s.equals("")) {
            return 0;
        }
        char[] str = s.toCharArray();
        int[] map = new int[256];
        for (int i = 0; i < 256; i++) {
            map[i] = -1;
        }
        map[str[0]] = 0;
        int N = str.length;
        int ans = 1;
        int pre = 1;
        for (int i = 1; i < N; i++) {
            pre = Math.min(i - map[str[i]], pre + 1);
            ans = Math.max(ans, pre);
            map[str[i]] = i;
        }
        return ans;
    }

    public static void main(String[] args) {
        lengthOfLongestSubstring("abcabcbb");
    }
}
